package com.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.atomic.AtomicInteger;

/**
 *code_repository_delta
 *@author huliangjun
 *@date 2018/11/30 11:23
 */
public class MapGraph {

    public static final int INFINITY = Integer.MAX_VALUE;

    private HashMap<String, Vertex> vertexMap = new HashMap<>();

    /**
     * 让vertexMap取得对Vertex对象的引用
     * @author huliangjun
     * @date 2018/11/30 11:31
     * @param vertexName
     * @return com.iqiyi.cola.robot.graph.Vertex
     */
    private Vertex getVertex(String vertexName) {

        Vertex v = vertexMap.get(vertexName);
        if (v == null) {
            v = new Vertex(vertexName);
            vertexMap.put(vertexName, v);
        }
        return v;
    }

    /**
     * 将距离初始化
     * @author huliangjun
     * @date 2018/11/30 11:31
     * @param
     * @return void
     */
    private void clearAll() {
        for (Iterator<Vertex> itr = vertexMap.values().iterator(); itr.hasNext(); ) {
            itr.next().reset();
        }
    }

    /**
     * 显示实际最短路径
     * @author huliangjun
     * @date 2018/11/30 11:32
     * @param dest
     * @return
     */
    private void getPath(Vertex dest,List<String> pathList,AtomicInteger level,TreeMap<Integer,TreeSet<JumpPoint>> pathMap) {

        if (dest.prePath != null) {
            getPath(dest.prePath,pathList,level,pathMap);
            System.out.print("-");
            TreeSet<JumpPoint> tmp = Edge.edgeMap.get(dest.prePath.name+"->"+dest.name).jumpPoint;
            System.out.print(tmp);
            Integer index = level.getAndIncrement();
            pathMap.put(index,tmp);
            System.out.print("-");
        }
        pathList.add(dest.name);
        System.out.print(dest.name);
    }

    /**
     * 添加一条新的边
     * @author huliangjun
     * @date 2018/11/30 11:32
     * @param sourceName
     * @param destName
     * @return void
     */
    public Edge addEdge(String sourceName, String destName) {

        Vertex v = getVertex(sourceName);
        Vertex w = getVertex(destName);
        v.adj.add(w);
        Edge edge = new Edge(sourceName,destName);
        Edge.edgeMap.put(sourceName+"->"+destName,edge);
        return edge;
    }

    /**
     * 显示一条路径
     * @author huliangjun
     * @date 2018/11/30 11:32
     * @param destName
     * @return void
     */
    public TreeMap<Integer,TreeSet<JumpPoint>> calculatorPath(String destName) throws NoSuchElementException {
          List<String> pathList = new ArrayList<>(10);
        AtomicInteger level = new AtomicInteger(1);
        TreeMap<Integer,TreeSet<JumpPoint>> pathMap = new TreeMap<>();
        System.out.print("To " + destName + ": ");
        Vertex w = vertexMap.get(destName);
        if (w == null) {

            throw new NoSuchElementException("Destination vertex not found!");
        } else if (w.dist == INFINITY) {

            System.out.println(destName + " id unreachable!");
        } else {
            getPath(w,pathList,level,pathMap);
            System.out.println();
        }
        return pathMap;
    }

    /**
     * 无权 最短路径计算
     * @author huliangjun
     * @date 2018/11/30 11:32
     * @param startName
     * @return void
     */
    public void unweighted(String startName) {

        clearAll();
        Vertex start = vertexMap.get(startName);
        if (start == null) {

            throw new NoSuchElementException("Start vertex not found!");
        }
        LinkedList<Vertex> q = new LinkedList<>();
        q.addLast(start);
        start.dist = 0;

        while (!q.isEmpty()) {
            Vertex v = q.removeFirst();
            for (Iterator<Vertex> itr = v.adj.iterator(); itr.hasNext(); ) {
                Vertex w = itr.next();
                if (w.dist == INFINITY) {
                    w.dist = v.dist + 1;
                    w.prePath = v;
                    q.addLast(w);
                }

            }
        }
    }
}
